一个快排有关的问题

问题来源于我的邀请赛里面的这道题

此题std

本来是一个很正常的贪心,然后神Sooke提出了一个结论,我整理后如下:

f(n)f(n)是这个题输出的数组中,满足a[i]=ia[i]=i的一段前缀的长度,那么

f(2)=2f(2)=2

f(2n)=1,n>1f(2^n)=1,n>1

f(n)=n的最大奇因子12,otherwisef(n)=\frac{\text{n的最大奇因子}-1}{2},otherwise

不太严谨的口胡证明

首先n4n\le4可以直接验证得到,对于n>4n>4

分析那个标程,可以发现f(n)f(n)就是注释标出的那行执行到的次数

如果某一时刻bb数组的[l,r)[l,r)区间中最小值在b[l]b[l]的位置,那么这就是一个好的状态

对于一个好的状态,如果rlr-l是奇数,22轮就能回到好的状态,并且这个过程中执行了一次注释标出的那行,于是

f(n)=f(n2)+1,n是奇数f(n)=f(n-2)+1,\text{n是奇数}

如果rlr-l是偶数,rl2\frac{r-l}{2}轮才能回到好的状态,这个过程中没有执行到注释标出的那行

f(n)=f(n2),n是偶数f(n)=f(\frac{n}{2}),\text{n是偶数}

结合n4n\le4的边界条件就可以推出来了